import java.util.LinkedList;
import java.util.Queue;

/**
 * 649. Dota2 参议院
 * https://leetcode-cn.com/problems/dota2-senate/
 */
public class Solutions_649 {
    public static void main(String[] args) {
        String str = "RD";  // output: "Radiant"
//        String str = "RDD";  // output: "Dire"
//        String str = "DDRRR";  // output: "Dire"

        String result = predictPartyVictory(str);
        System.out.println(result);
    }

    public static String predictPartyVictory(String senate) {
        Queue<Integer> rQueue = new LinkedList<>();
        Queue<Integer> dQueue = new LinkedList<>();
        char[] arr = senate.toCharArray();
        int len = arr.length;
        // 记录索引
        for (int i = 0; i < len; i++) {
            if (arr[i] == 'R') {
                rQueue.add(i);
            } else {
                dQueue.add(i);
            }
        }
        // 两阵营都有投票权时，将一直比较，直到一方没有投票权（即队列为空）
        while (!rQueue.isEmpty() && !dQueue.isEmpty()) {
            int r = rQueue.poll(), d = dQueue.poll();
            // 索引靠前的，可以投票让对手丧失投票权，从而自己进行下一轮的投票
            if (r < d) {
                rQueue.add(r + len);
            } else {
                dQueue.add(d + len);
            }
        }
        // 最终拥有投票权的一方将获胜
        return rQueue.isEmpty() ? "Dire" : "Radiant";
    }
}
